home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 / Ham Radio 2000.iso / ham2000 / tcp_ip / tnos / tnos100s / lzw.c < prev    next >
C/C++ Source or Header  |  1993-04-30  |  15KB  |  580 lines
  1. /*        SM0RGV data compression routines.
  2.  * This file implements the Lempel-Ziv Welch (LZW) data compression
  3.  * algorithm but with a variable code size, as in GIF format files.
  4.  *
  5.  * Copyright 1990 by Anders Klemets, SM0RGV. Permission granted for
  6.  * non-commercial distribution only.
  7.  */
  8.  
  9. #include <ctype.h>
  10. #include "global.h"
  11. #include "config.h"
  12. #ifdef    LZW
  13. #include "mbuf.h"
  14. #include "proc.h"
  15. #include "lzw.h"
  16. #include "socket.h"
  17. #include "usock.h"
  18. #include "session.h"
  19. #include "cmdparse.h"
  20.  
  21. static void fastencode __ARGS((struct usock *up,char data));
  22. static void morebits __ARGS((struct lzw *lzw));
  23. static void cleartbl __ARGS((struct lzw *lzw));
  24. static void addtobuffer __ARGS((struct usock *up,int32 code));
  25. static void addchar __ARGS((char data,struct lzw *lzw));
  26. static void getstring __ARGS((int32 code,struct lzw *lzw));
  27. static char firstchar __ARGS((int32 code,struct lzw *lzw));
  28. static void decodetbl __ARGS((int32 code,struct lzw *lzw));
  29. static int32 nextcode __ARGS((struct usock *up));
  30.  
  31. int
  32. dolzw(argc,argv,p)
  33. int argc;
  34. char *argv[];
  35. void *p;
  36. {
  37.     if(argc > 1) {
  38.         switch(tolower(*argv[1])) {
  39.         case 'm':
  40.             if(argc == 2) {
  41.                 tprintf("LZW mode: %s\n",Lzwmode ? "fast" : "compact");
  42.             } else {
  43.                 Lzwmode = (tolower(*argv[2]) == 'f');
  44.             }
  45.             return 0;
  46.         case 'b':
  47.             argc--;
  48.             argv++;
  49.             return setintrc(&Lzwbits,"LZW bits",argc,argv,9,16);
  50.         case '=':
  51.             if(argc == 3) {
  52.                 struct session *sp;
  53.                 if((sp = sessptr(argv[2])) != NULLSESSION) {
  54.                     lzwinit(sp->s,Lzwbits,Lzwmode);
  55.                 }
  56.             }
  57.             return 0;
  58.         }
  59.     }
  60.     tputs("Usage: lzw <mode|bits>\n");
  61.     return -1;
  62. }
  63.  
  64. /* Initialize a socket for compression. Bits specifies the maximum number
  65.  * of bits per codeword. The input and output code tables might grow to
  66.  * about (2^bits * 3) bytes each. The bits parameter does only serve as a
  67.  * recommendation for the decoding, the actual number of bits may be
  68.  * larger, but not never more than 16.
  69.  */
  70. void
  71. lzwinit(s,bits,mode)
  72. int s;        /* socket to operate on */
  73. int bits;    /* maximum number of bits per codeword */
  74. int mode;    /* compression mode, LZWCOMPACT or LZWFAST */
  75. {
  76.     struct usock *up;
  77.     if((up = itop(s)) == NULLUSOCK)
  78.         return;
  79.     up->zout = (struct lzw *) callocw(1,sizeof(struct lzw));
  80.     up->zin = (struct lzw *) callocw(1,sizeof(struct lzw));
  81.     up->zout->codebits = LZWBITS;
  82.     if(bits < LZWBITS)
  83.         up->zout->maxbits = LZWBITS;
  84.     if(bits > 16 || bits == 0)
  85.         up->zout->maxbits = 16;
  86.     if(bits >= LZWBITS && bits <= 16)
  87.         up->zout->maxbits = bits;
  88.     up->zout->nextbit = 0;
  89.     up->zout->prefix = -1;
  90.     up->zout->version = -1;
  91.     up->zout->code = -1;
  92.     up->zout->mode = mode;
  93.     up->zout->next = ZFLUSH + 1;    /* used only in LZWFAST mode */
  94.     up->zin->codebits = LZWBITS;
  95.     up->zin->maxbits = -1;
  96.     up->zin->nextbit = 0;
  97.     up->zin->prefix = -1;
  98.     up->zin->version = -1;
  99.     up->zin->code = -1;
  100.     up->zin->next = ZFLUSH + 1;
  101.     up->zin->mode = LZWCOMPACT;
  102.     up->zin->buf = NULLBUF;
  103. }
  104.  
  105. void
  106. lzwfree(up)
  107. struct usock *up;
  108. {
  109.     if(up->zout != NULLLZW) {
  110.         cleartbl(up->zout);
  111.         free((char *)up->zout);
  112.         up->zout = NULLLZW;
  113.     }
  114.     if(up->zin != NULLLZW) {
  115.         cleartbl(up->zin);
  116.         free_q(&up->zin->buf);
  117.         free((char *)up->zin);
  118.         up->zin = NULLLZW;
  119.     }
  120. }
  121. /* LZW encoding routine.
  122.  * See if the string specified by code + data is in the string table. If so,
  123.  * set prefix equal to the code of that string. Otherwise insert code + data
  124.  * in the string and set prefix equal to data.
  125.  */
  126. void
  127. lzwencode(s,data)
  128. int s;
  129. char data;
  130. {
  131.     struct usock *up;
  132.     register struct lzw *lzw;
  133.     int32 code, pagelim;
  134.     register int16 i,j;
  135.  
  136.     if((up = itop(s)) == NULLUSOCK)
  137.         return;
  138.     lzw = up->zout;
  139.     code = up->zout->prefix;
  140.     /* the first byte sent will be the version number */
  141.     if(lzw->version == -1) {
  142.         lzw->version = ZVERSION;
  143.         up->obuf->data[up->obuf->cnt++] = lzw->version;
  144.         /* then send our recommended maximum number of codebits */
  145.         up->obuf->data[up->obuf->cnt++] = lzw->maxbits;
  146.     }
  147.     lzw->cnt++;
  148.     if(code == -1) {
  149.         lzw->prefix = (int32) uchar(data);
  150.         return;
  151.     }
  152.     if(lzw->mode == LZWFAST) {
  153.         fastencode(up,data);
  154.         return;
  155.     }
  156.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  157.     if(code <= ZFLUSH)
  158.         i = j = 0;
  159.     else {
  160.         i = (code - ZFLUSH) / LZWBLK;
  161.         j = (code - ZFLUSH) % LZWBLK;
  162.     }
  163.     if(lzw->tu.tbl == (struct zentry **)0)
  164.         lzw->tu.tbl = (struct zentry **) callocw(1,
  165.             sizeof(struct zentry *) * pagelim);
  166.     for(;;) {
  167.         if(itop(s) == NULLUSOCK) /* the connection has been closed */
  168.             return;
  169.         if(up->zout == NULLLZW) /* ...or is about to be closed */
  170.             return;
  171.         if(lzw->tu.tbl[i] == (struct zentry *)0) {
  172.             lzw->tu.tbl[i] = (struct zentry *)
  173.                 mallocw(LZWBLK * sizeof(struct zentry));
  174.             memset((char *)lzw->tu.tbl[i], 0xff,
  175.                 LZWBLK * sizeof(struct zentry));
  176.         }
  177.         while(j < LZWBLK) {
  178.             if(lzw->tu.tbl[i][j].data == data &&
  179.                 lzw->tu.tbl[i][j].code == (int16) code) {
  180.                 lzw->prefix = (int32)(i * LZWBLK + j +
  181.                               ZFLUSH + 1);
  182.                 return;
  183.             }
  184.             if(lzw->tu.tbl[i][j].code == 0xffff) {
  185.                 lzw->tu.tbl[i][j].code = (int16) code;
  186.                 lzw->tu.tbl[i][j].data = data;
  187.                 addtobuffer(up,code);
  188.                 lzw->prefix = (int32) uchar(data);
  189.                 lzw->next++;
  190.                 if(lzw->next ==    (int32) 1 << lzw->codebits)
  191.                     /* the current table is now full */
  192.                     morebits(lzw);
  193.                 if(lzw->next + 1 == (int32)
  194.                         1 << lzw->maxbits) {
  195.                 /* The last codeword has been reached.
  196.                  * (Or last - 1.) Signal this and start all
  197.                  * over again.
  198.                  */
  199.                     addtobuffer(up,lzw->prefix);
  200.                        if(lzw->next + 1 == (int32)
  201.                             1 << lzw->codebits)
  202.                         morebits(lzw);
  203.                     addtobuffer(up,ZCC);
  204.                     cleartbl(lzw);
  205.                 }
  206.                 return;
  207.             }
  208.             ++j;
  209.         }
  210.         pwait(NULL);
  211.         ++i;
  212.         j = 0;
  213.     }
  214. }
  215.  
  216. /* Used when LZWFAST mode is selected. Memory usage approx. (2^bits * 5)
  217.  * bytes.
  218.  */
  219. static void
  220. fastencode(up,data)
  221. struct usock *up;
  222. char data;
  223. {
  224.     register struct zfast *z;
  225.     register struct mbuf *bp;
  226.     register struct lzw *lzw = up->zout;
  227.     int32 code = up->zout->prefix;
  228.     register int16 cnt, h;
  229.  
  230.     if(lzw->tu.bpp == NULLBUFP)
  231.         lzw->tu.bpp = (struct mbuf **) callocw(1,
  232.             sizeof(struct mbuf *) * ZHASH);
  233.     h = lobyte(code);
  234.     h ^= hibyte(code);
  235.     h ^= data;
  236.     h = h % ZHASH;
  237.     if(lzw->tu.bpp[h] == NULLBUF)
  238.         lzw->tu.bpp[h] = ambufw(LZWBLK);
  239.     bp = lzw->tu.bpp[h];
  240.     cnt = bp->cnt / sizeof(struct zfast);
  241.     z = (struct zfast *) bp->data;
  242.     while(cnt > 0) {
  243.         if(z->data == data && z->code == (int16) code) {
  244.             lzw->prefix = (int32) z->owncode;
  245.             return;
  246.         }
  247.         z++;
  248.         if(--cnt == 0) {
  249.             if(bp->next == NULLBUF)
  250.                 break;
  251.             bp = bp->next;
  252.             cnt = bp->cnt / sizeof(struct zfast);
  253.             z = (struct zfast *) bp->data;
  254.         }
  255.     }
  256.     if(bp->size - bp->cnt >= sizeof(struct zfast)) {
  257.         z = (struct zfast *) &bp->data[bp->cnt];
  258.         bp->cnt += sizeof(struct zfast);
  259.     }
  260.     else {
  261.         bp->next = ambufw(LZWBLK);
  262.         z = (struct zfast *) bp->next->data;
  263.         bp->next->cnt = sizeof(struct zfast);
  264.     }
  265.     z->code = (int16) code;
  266.     z->data = data;
  267.     z->owncode = (int16) lzw->next++;
  268.     addtobuffer(up,code);
  269.     lzw->prefix = (int32) uchar(data);
  270.     if(lzw->next == (int32) 1 << lzw->codebits) {
  271.         /* Increase the number of bits per codeword */
  272.         morebits(lzw);
  273.     }
  274.     if(lzw->next + 1 == (int32) 1 << lzw->maxbits) {
  275.         /* The last codeword has been reached. (Or last - 1.)
  276.          * Signal this and start all over again.
  277.          */
  278.         addtobuffer(up,lzw->prefix);
  279.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  280.             morebits(lzw);
  281.         addtobuffer(up,ZCC);
  282.         cleartbl(lzw);
  283.     }
  284.     pwait(NULL);
  285. }
  286.  
  287. /* increase the number of significant bits in the codewords, and increase
  288.  * the size of the string table accordingly.
  289.  */
  290. static void
  291. morebits(lzw)
  292. struct lzw *lzw;
  293. {
  294.     struct zentry **newt;
  295.     int32 pagelim, oldp;
  296.     oldp = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  297.     lzw->codebits++;
  298.     if(lzw->mode == LZWFAST)
  299.         return;
  300.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  301.     newt = (struct zentry **) callocw(1,sizeof(struct zentry *)*pagelim);
  302.     memcpy(newt,lzw->tu.tbl,sizeof(struct zentry *) * oldp);
  303.     free((char *)lzw->tu.tbl);
  304.     lzw->tu.tbl = newt;
  305. }
  306.  
  307. static void
  308. cleartbl(lzw)
  309. struct lzw *lzw;
  310. {
  311.     int32 pagelim,i;
  312.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  313.     lzw->codebits = LZWBITS;
  314.     lzw->prefix = -1;
  315.     lzw->next = ZFLUSH + 1;
  316.     if(lzw->tu.p == NULL)
  317.         return;
  318.     if(lzw->mode == LZWCOMPACT)
  319.         for(i=0; i < pagelim; ++i)
  320.             free((char *)lzw->tu.tbl[i]);
  321.     else
  322.         for(i=0; i < ZHASH; ++i)
  323.             free_p(lzw->tu.bpp[i]);
  324.     free((char *)lzw->tu.p);
  325.     lzw->tu.p = NULL;
  326. }
  327. /* Add a codeword to the code stream. Nextbit indicates at which bit in the
  328.  * code stream should be written first. The codeword ZFLUSH is used to
  329.  * pad the buffer to a byte boundary when the buffer will be flushed.
  330.  * The remaining bits of the ZFLUSH codeword are sent in the next buffer.
  331.  */
  332. static void
  333. addtobuffer(up,code)
  334. struct usock *up;
  335. int32 code;
  336. {
  337.     if(up->zout->code != -1) {
  338.         /* Insert remaining bits of ZFLUSH codeword */
  339.         up->obuf->data[up->obuf->cnt] =
  340.              up->zout->code >> up->zout->flushbit;
  341.         if(up->zout->flushbit + 8 >= up->zout->codebits) { /* done */
  342.             up->zout->nextbit = (up->zout->codebits -
  343.                         up->zout->flushbit) % 8;
  344.             if(up->zout->nextbit == 0)
  345.                 ++up->obuf->cnt;
  346.             up->zout->code = -1;
  347.         }
  348.         else {
  349.             /* not done yet */
  350.             ++up->obuf->cnt;
  351.             up->zout->flushbit += 8;
  352.             addtobuffer(up,code);
  353.             return;
  354.         }
  355.     }
  356.     /* normal codewords are treated here */
  357.     if(up->zout->nextbit == 0) {
  358.         /* we are at a byte boundary */
  359.         if(code == ZFLUSH) {
  360.             up->zout->flushbit = 0;
  361.             up->zout->code = ZFLUSH;
  362.             return;
  363.         }
  364.         up->obuf->data[up->obuf->cnt++] = (char) code;
  365.     }
  366.     else
  367.         up->obuf->data[up->obuf->cnt++] |= code << up->zout->nextbit;
  368.     if(code == ZFLUSH) {
  369.         /* interrupt here and save the rest of the ZFLUSH
  370.          * codeword for later.
  371.          */
  372.         up->zout->flushbit = 8 - up->zout->nextbit;
  373.         up->zout->code = ZFLUSH;
  374.         return;
  375.     }
  376.     up->obuf->data[up->obuf->cnt] = code >> 8 - up->zout->nextbit;
  377.     /* start on a third byte if necessary */
  378.     if(16 - up->zout->nextbit < up->zout->codebits)
  379.         up->obuf->data[++up->obuf->cnt] =
  380.                     code >> 16 - up->zout->nextbit;
  381.     up->zout->nextbit = (up->zout->nextbit + up->zout->codebits) % 8;
  382.     if(up->zout->nextbit == 0)
  383.         ++up->obuf->cnt;
  384. }
  385.  
  386. void
  387. lzwflush(up)
  388. struct usock *up;
  389. {
  390.     /* interrupt the encoding process and send the prefix codeword */
  391.     if(up->zout->prefix != -1) {
  392.         addtobuffer(up,up->zout->prefix);
  393.            if(up->zout->next + 1 == (int32) 1 << up->zout->codebits)
  394.             morebits(up->zout);
  395.         up->zout->prefix = -1;
  396.     }
  397.     /* signal this by sending the ZFLUSH codeword */
  398.     addtobuffer(up,ZFLUSH);
  399. }
  400.  
  401. int
  402. lzwdecode(up)
  403. struct usock *up;
  404. {
  405.     int32 code,data;
  406.     if(up->zin->version == -1 && (up->zin->version = PULLCHAR(&up->ibuf))
  407.        == -1)
  408.         return -1;
  409.     if(up->zin->maxbits == -1) {
  410.         /* receive a recommended value for the maximum no of bits */
  411.         if((up->zin->maxbits = PULLCHAR(&up->ibuf)) == -1)
  412.             return -1;
  413.         if(up->zout->maxbits > up->zin->maxbits) {
  414.             if(up->zout->codebits > up->zin->maxbits) {
  415.                 /* We are already using more bits than our
  416.                  * peer want us to, so clear the encoding
  417.                  * table immediately.
  418.                  */
  419.                 addtobuffer(up,up->zout->prefix);
  420.                 if(up->zout->next + 1 == (int32)
  421.                    1 << up->zout->codebits)
  422.                     morebits(up->zout);
  423.                 addtobuffer(up,ZCC);
  424.                 cleartbl(up->zout);
  425.             }
  426.             up->zout->maxbits = up->zin->maxbits;
  427.         }
  428.     }
  429.     for(;;) {
  430.         if((data = PULLCHAR(&up->zin->buf)) != -1)
  431.             return (int) data;
  432.         if((code = nextcode(up)) == -1)
  433.             return -1;
  434.         decodetbl(code,up->zin);
  435.         up->zin->cnt += len_p(up->zin->buf);
  436.     }
  437. }
  438.  
  439. static void
  440. addchar(data,lzw)
  441. char data;
  442. struct lzw *lzw;
  443. {
  444.     lzw->buf = pushdown(lzw->buf,1);
  445.     *lzw->buf->data = data;
  446. }
  447. static void
  448. getstring(code,lzw)
  449. int32 code;
  450. struct lzw *lzw;
  451. {
  452.     int16 i,j;
  453.     for(;;) {
  454.         if(code < ZFLUSH) {
  455.             addchar(uchar(code),lzw);
  456.             return;
  457.         }
  458.         i = (code - ZFLUSH - 1) / LZWBLK;
  459.         j = (code - ZFLUSH - 1) % LZWBLK;
  460.         addchar(lzw->tu.tbl[i][j].data,lzw);
  461.         code = (int32) lzw->tu.tbl[i][j].code;
  462.     }
  463. }
  464. static char
  465. firstchar(code,lzw)
  466. int32 code;
  467. struct lzw *lzw;
  468. {
  469.     int16 i,j;
  470.     for(;;) {
  471.         if(code < ZFLUSH)
  472.             return uchar(code);
  473.         i = (code - ZFLUSH - 1) / LZWBLK;
  474.         j = (code - ZFLUSH - 1) % LZWBLK;
  475.         code = (int32) lzw->tu.tbl[i][j].code;
  476.     }
  477. }
  478. static void
  479. decodetbl(code,lzw)
  480. int32 code;
  481. struct lzw *lzw;
  482. {
  483.     register int16 i,j;
  484.     int32 pagelim;
  485.  
  486.     if(code > lzw->next) {
  487.         printf("LZW protocol error, process '%s'\n",Curproc->name);
  488.         return;
  489.     }
  490.     if(lzw->buf == NULLBUF) {
  491.         lzw->buf = ambufw(512);
  492.         /* allow us to use pushdown() later */
  493.         lzw->buf->data += lzw->buf->size;
  494.     }
  495.     if(lzw->prefix == -1) {
  496.         getstring(code,lzw);
  497.         lzw->prefix = code;
  498.         return;
  499.     }
  500.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  501.     if(lzw->tu.tbl == (struct zentry **)0)
  502.         lzw->tu.tbl = (struct zentry **) callocw(1,
  503.                 sizeof(struct zentry *) * pagelim);
  504.     if(code < ZFLUSH)
  505.         goto intable;
  506.     i = (code - ZFLUSH - 1) / LZWBLK;
  507.     j = (code - ZFLUSH - 1) % LZWBLK;
  508.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  509.         lzw->tu.tbl[i] = (struct zentry *)
  510.                 mallocw(LZWBLK * sizeof(struct zentry));
  511.         memset((char *)lzw->tu.tbl[i], 0xff,
  512.                 LZWBLK * sizeof(struct zentry));
  513.     }
  514.     if(lzw->tu.tbl[i][j].code == 0xffff) {
  515.         lzw->tu.tbl[i][j].data = firstchar(lzw->prefix,lzw);
  516.         lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  517.         getstring(code,lzw);
  518.         lzw->next = code + 1;
  519.         lzw->prefix = code;
  520.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  521.             morebits(lzw);
  522.         return;
  523.     }
  524. intable:
  525.     getstring(code,lzw);
  526.     i = (lzw->next - ZFLUSH - 1) / LZWBLK;
  527.     j = (lzw->next - ZFLUSH - 1) % LZWBLK;
  528.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  529.         lzw->tu.tbl[i] = (struct zentry *)
  530.                 mallocw(LZWBLK * sizeof(struct zentry));
  531.         memset((char *)lzw->tu.tbl[i], 0xff,
  532.                 LZWBLK * sizeof(struct zentry));
  533.     }
  534.     lzw->tu.tbl[i][j].data = firstchar(code,lzw);
  535.     lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  536.     lzw->next++;
  537.     lzw->prefix = code;
  538.     if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  539.         morebits(lzw);
  540. }
  541.  
  542. /* extract the next codeword from the input stream */
  543. static int32
  544. nextcode(up)
  545. struct usock *up;
  546. {
  547.     int32 code;
  548.     if(up->zin->code == -1) {    /* read the first character */
  549.         if((code = PULLCHAR(&up->ibuf)) == -1)
  550.             return -1;
  551.         up->zin->code = code >> up->zin->nextbit;
  552.     }
  553.     if(up->ibuf == NULLBUF)        /* next byte is not available yet */
  554.         return -1;
  555.     /* continue assembling the codeword */
  556.     up->zin->code |= ((int32) uchar(*up->ibuf->data) <<
  557.             8 - up->zin->nextbit) & (((int32) 1 <<
  558.             up->zin->codebits) - 1);
  559.     if(16 - up->zin->nextbit < up->zin->codebits) {
  560.         (void) PULLCHAR(&up->ibuf);
  561.         up->zin->nextbit -= 8; /* pull bits from a third byte */
  562.         return nextcode(up);
  563.     }
  564.     code = up->zin->code;
  565.     up->zin->code = -1;
  566.     up->zin->nextbit = (up->zin->nextbit + up->zin->codebits) % 8;
  567.     if(up->zin->nextbit == 0)
  568.         (void) PULLCHAR(&up->ibuf);
  569.     if(code == ZCC) {
  570.         cleartbl(up->zin);
  571.         return nextcode(up);
  572.     }
  573.     if(code == ZFLUSH) {
  574.         up->zin->prefix = -1;
  575.         return nextcode(up);
  576.     }
  577.     return code;
  578. }
  579. #endif
  580.